Minimum Knight Moves

Description#

We have an infinite chessboard with coordinates starting from -infinity to infinity. Our knight starts in square (0, 0).

The knight has eight possible moves at a given time. It can move in an L-shape, meaning it can move two squares in any direction vertically and then one square horizontally or two squares in any direction horizontally and then one square vertically.

You need to find the minimum moves the knight needs to get from the origin (0,0) to the coordinates (x,y). We will assume that the provided coordinates are always reachable and the constraint |x| + |y| <= 300 holds.

For example, given the input coordinate, (5, 5) you have to find the minimum number of moves required for the knight to get from the origin to the coordinate. In this case, the program will output four because the knight needs four moves to get to the coordinate.

Coding exercise#

Solution#

Notice that the knight’s movements to both the positive and negative coordinates and the axis are symmetrical. The same number of moves are required to get to both the positive and negative coordinates. The knight can move in any of the eight directions at any given time by adding the following coordinates, [{1, 2}, {2, 1}, {-1, 2}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {2, -1}] to the current coordinates.

Therefore, we can avoid the negative coordinates and create our solution around the first quadrant, keeping the coordinates positive. The origin is fixed, and we can use this to transform our input coordinates. We can take the absolute value of the coordinate and use it as our starting point. This way, we know which direction we should move in. In this case, we will only move in two directions by adding the following coordinates to the current coordinates, [{-1, -2}, {-2, -1}]. We will only explore the absolute values of the coordinates.

Here is how we will implement this solution:

1. Take the absolute values of the coordinates (x, y).
2. Manually initialize the map with the minimum moves it takes to get to the origin’s coordinates. The map contains the coordinate as the key and minimum knight it takes to get to the origin as the value.
3. Start from the input coordinates and explore all the squares in a depth-first manner back to the origin.
4. If the coordinate has already been explored, we can return that value; otherwise, we will explore the next possible coordinates the knight can move to.
5. We pick the path with the minimum moves and backtrack to the input coordinate.

Let’s review the solution:

Complexity measures#

Time complexity#

We are dealing with a submatrix starting from the origin and ending at [x, y]. The origin is fixed, and we might have to traverse all the squares. Therefore, the time complexity will be $O(\|X\| * \|Y\|)$.

Space complexity#

We might have to store the moves for all the squares, so the space complexity will be quadratic as well.